package 排序算法;

/**
 *     begin = 0                   end = 7
 * 数据：{1, 56, 32, 56, 12, 77, 88, 21};
 * 选择排序：
 * 1.从上面的数据中，随机选择一个数字作为轴点（记为P），与begin交换，然后备份begin位置
 * 2.然后从右向左扫描，
 *      如果比P大，end -- ，继续从右向左扫描
 *      如果比P小，就把数组覆盖begin的位置，然后begin++。开始从左往右扫描
 *   从左往右扫描
 *      如果比P大，就把数组覆盖end的位置，然后end--。开始从右向左扫描
 *      如果比P小，begin++，继续从左往右扫描
 *   最终返回轴点的位置，拆分两个子序列。
 *
 */
public class 快速排序 {

    private static Integer[] arrays;

    public static void main(String[] args) {
        arrays = new Integer[]{1, 56, 32, 56, 12, 77, 88, 21};

        sort(0, arrays.length);

        for (int i = 0; i < arrays.length; i++) {
            System.out.print(arrays[i] + "_");
        }
    }

    private static void sort(int begin, int end) {
        //切割到不能切割条件
        if (end - begin < 2) return;

        //确定轴点下标
        int mid = privotIndex(begin, end);
        //不断进行分组切割
        sort(begin, mid);
        sort(mid + 1, end);
    }

    private static int privotIndex(int begin, int end) {
        //随机生成一个轴点，与begin交换位置
        swap(begin, begin + (int) (Math.random() * (end - begin)));
        int privot = arrays[begin];
        //end的值指向最后一个元素
        end--;
        while (begin < end) {
            //从右往左扫描
            while (begin < end) {
                if (arrays[end] > privot) {
                    end--;
                } else {
                    //覆盖begin位置的值
                    arrays[begin++] = arrays[end];
                    break;
                }
            }
            //从左往右扫描
            while (begin < end) {
                if (arrays[begin] < privot) {
                    begin++;
                } else {
                    arrays[end--] = arrays[begin];
                    break;
                }
            }
        }

        //最后将轴点覆盖 begin==end
        arrays[begin] = privot;
        return begin;
    }

    private static void swap(int i1, int i2) {
        int tmp = arrays[i1];
        arrays[i1] = arrays[i2];
        arrays[i2] = tmp;
    }

}
